package ua.mykola.backtracking;

import java.util.LinkedList;
import java.util.List;

public class AllStringCombinations2 {

	public static void main(String[] args) {
		List<String> list = new AllStringCombinations2().combinations("abcd");
		System.out.println(list);
		System.out.println(list.size());
	}

	public List<String> combinations(String str) {
		List<String> combs = new LinkedList<String>();
		combinations(str.toCharArray(), 0, combs);
		return combs;
	}

	private List<String> combinations(char[] chars, int index, List<String> combs) {

		if (index == chars.length) {
			combs.add("");
			return combs;
		}

		combinations(chars, index + 1, combs);

		List<String> newCombs = new LinkedList<String>();
		for (String string : combs) {
			newCombs.add(chars[index] + string);
		}
		combs.addAll(newCombs);

		return combs;
	}
}
